package BinTree;

import LeetCode.ListNode;
import sun.reflect.generics.tree.Tree;

public class MyBinTree {
    public static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public static TreeNode build(){
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        nodeE.right = nodeH;
        return nodeA;
    }

    //统计一颗二叉树的结点个数
    public static int getNodes(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + getNodes(root.left) + getNodes(root.right);
    }

    //统计一颗二叉树的叶子结点个数
    public static int getLeafNodes(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    //判断一颗二叉树中是否包含指定元素
    public static boolean contains(TreeNode root,char val){
        if(root == null){
            return false;
        }
        if(root.val == val){
            return true;
        }
        return contains(root.left,val) || contains(root.right,val);
    }

    //求当前二叉树的高度
    public static int hight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHight = hight(root.left);
        int rightHight = hight(root.right);
        int MaxHight = Math.max(leftHight,rightHight);
        return 1 + MaxHight;
    }

    //求第k层的结点个数
    public static int getKLevelNodes(TreeNode root,int k){
        if(root == null || k <= 0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodes(root.left,k - 1) + getKLevelNodes(root.right,k - 1);
    }
    //先序遍历
    public static void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + ",");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //后序遍历
    public static void  postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public static void main(String[] args) {
        TreeNode root = build();
//        System.out.println("前序遍历结果为:");
//        preOrder(root);
//        System.out.println("中序遍历结果为:");
//        inOrder(root);
//        postOrder(root);
//        System.out.println(getNodes(root));
//        System.out.println(getLeafNodes(root));
//        System.out.println(contains(root,'G'));
//        System.out.println(hight(root));
        System.out.println(getKLevelNodes(root,3));
    }
}
